package solution.design;

/**
 * @author zhangmin
 * @create 2022-05-23 13:28
 * 211. 添加与搜索单词 - 数据结构设计
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 *
 * 思路：使用前缀树实现
 */
public class WordDictionary {
    private Trie root;
    //初始化词典对象
    public WordDictionary() {
        root=new Trie();
    }
    //将 word 添加到数据结构中，之后可以对它进行匹配
    public void addWord(String word) {
        root.insert(word);
    }
    //如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
    public boolean search(String word) {
        return dfs(word,0,root);
    }
    private boolean dfs(String word,int index,Trie node){
        if (index==word.length()){
            return node.isEnd();
        }
        char c=word.charAt(index);
        if (Character.isLetter((c))){
            int indexChar=c-'a';
            Trie child=node.getChildren()[indexChar];
            if (child!=null&&dfs(word,index+1,child)){
                return true;
            }
        }else {
            for (int i=0;i<26;i++){
                Trie child=node.getChildren()[i];
                if (child!=null&&dfs(word,index+1,child)){
                    return true;
                }
            }
        }
        return false;
    }
}

class Trie{
    private Trie[] children;
    private boolean isEnd;
    public Trie(){
        children=new Trie[26];
        isEnd=false;
    }
    public void insert(String word){
        Trie cur=this;
        for (int i = 0; i < word.length(); i++) {
            char ch=word.charAt(i);
            int index=ch-'a';
            if (cur.children[index]==null){
                cur.children[index]=new Trie();
            }
            cur=cur.children[index];
        }
        cur.isEnd=true;
    }

    public Trie[] getChildren() {
        return children;
    }

    public boolean isEnd() {
        return isEnd;
    }
}